//剑指offer28题，数组中出现超过一半的数字

//这个方法是用图来做的
import java.util.HashMap;
import java.util.Map;
public class Solution {
    public int MoreThanHalfNum_Solution(int [] array) {
        if(array==null||array.length==0)return 0;
        Map<Integer,Integer> map=new HashMap<>();
        for(int i=0;i<array.length;i++){
            if(map.get(array[i])==null){
                map.put(array[i],1);
        }else{
                int value=map.get(array[i]);
                map.put(array[i],value+1);
            }
        }
        int max=0;
        for(Map.Entry<Integer,Integer> entry:map.entrySet()){
            if(max<entry.getValue()&&entry.getValue()>(array.length/2)){
                max=entry.getKey();
            }
        }
    return max;
    }
}

//优质答案
//用preValue记录上一次访问的值，count表明当前值出现的次数，
//如果下一个值和当前值相同那么count++；如果不同count--，
//减到0的时候就要更换新的preValue值了，因为如果存在超过数组长度一半的值，
//那么最后preValue一定会是该值。
public class Solution {
    public int MoreThanHalfNum_Solution(int [] array) {
        if(array==null||array.length==0)return 0;
		int preValue=array[0];//用来记录上一次的数据
		int count=1;//preValue出现的次数
		for(int i=1;i<array.length;i++){//得到出现次数最多的那个数记为preValue
			if(array[i]==preValue){
				count++;
			}else{
				count--;
				if(count==0){//当count为0，重新选择preValue
					preValue=array[i];
					count=1;
				}
			}
		}
		int num=0;
		for(int i=0;i<array.length;i++){//计算preValue出现的次数并比较是否大于数组的一半
			if(array[i]==preValue){
				num++;
			}
		}
	return (num>array.length/2)?preValue:0;
	}
}
